Date: Wed, 20 Nov 1996 22:38:24 GMT
Server: NCSA/1.5.1
Last-modified: Tue, 18 Jul 1995 02:26:33 GMT
Content-type: text/html
Content-length: 1477


<html>
<head>
<title>CIS870 syllabus fall 1995</title>
</head>
<body>

<h1>CIS870: Computability Theory</h1>
Autumn 1995
<p>

MWF 10:30pm  N127<br>
Dave Schmidt, Instructor<br>
Office: N219A, 532-6350 <br>
<p>
Text: <i>Computability</i>, by Nigel Cutland.
Supplemental notes will be available later in the course.
<p>

<h2>Objectives: to understand and appreciate</h2>
<ul>
<li>
the fundamental requirements of an algorithm and a programming language
<li>
what can and cannot be programmed
<li>
fundamental counting techniques for computer science
<li>
time and space complexities of solvable problems
<li>
applications of the above concepts
</ul>

<h2>Lectures:</h2>

TOPIC/NUMBER OF LECTURES
<ul>
<li>
Minimal assembly language      1
<li>
Capabilities of assembly language; equivalent formulations:
mu-recursive functions, Turing machines; Church's thesis    2
<li>
Basic enumeration techniques; s-m-n theorem    1
<li>
Universal algorithms   1
<li>
Undecidable problems   2
<li>
Recursively enumerable sets    1
<li>
Reducibility   1
<li>
The recursion theorems 2
<li>
Introduction to complexity theory      1
<li>
The complexity classes P and NP        2
</ul>


<h2>Prerequisites:</h2>
CIS770 or CIS775.

<h2>Grading:</h2>
is based primarily on homework exercises, but there might also
be one or two take-home exams.


<hr>
<address>Dave Schmidt (<!WA0><a href=
"http://www.cis.ksu.edu/htbin/finger?schmidt@cis.ksu.edu">schmidt@cis.ksu.edu</a
>)
</address>

</body>
</html>


